package 力扣_二分查找;

/**
 * @author zx
 * @create 2022-06-07 10:48
 */
public class 在排序数组中查找数字I_53 {
    /**
     * @return 官方代码不冗余
     */
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    //二分查找没找到返回比target大的第一个数
    private int helper(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    /**
     * @return 根据自己的模板,两次二分
     */
    public int search2(int[] nums, int target) {
        int left = left_bound(nums,target);
        int right = right_bound(nums,target);
        if(left == -1 && right == -1){
            return 0;
        }
        return right - left + 1;
    }
    public static int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }
    public static int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里检查right越界的情况
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
}
